Le prime informazioni sulla chiesa risalgono all'XI secolo: in quel periodo, la chiesa fa parte di un'abbazia benedettina dedicata ai Santi Pietro e Paolo. Il complesso, oltretutto, era stato fondato nelle vicinanze di un'importante strada consolare, la Via Emilia, che rendeva il luogo ideale per l'insediamento di un monastero. Ben presto, attorno all'abbazia si sviluppa un centro abitato, quello che oggi è ancora il Borgo di San Giuliano, sulla sponda occidentale del fiume Marecchia. Durante il Medioevo la chiesa doveva presentarsi a tre navate e caratterizzata dalle tecniche costruttive e architettoniche del romanico. Nel Duecento, inoltre, assume la dedica a San Giuliano, in corrispondenza della diffusione del culto del Santo. Fra il 1553 e il 1575, ormai diventato il fulcro religioso più importante della città, il monastero, assieme alla chiesa, viene restaurato e in parte ricostruito. La chiesa assume l'aspetto ancora visibile oggi, a navata unica.

La chiesa di San Giuliano contiene numerosi dipinti, fra i quali ne spiccano due di notevole pregio. Il primo è il polittico di Bittino da Faenza con le Storie di San Giuliano, opera risalente ad inizio del Quattrocento conservata nella terza cappella a sinistra, il secondo è la pala centrale dell'abside, il Martirio di San Giuliano (prima del 1583), ritenuta una delle ultime, e più significative, opere di Paolo Veronese. Nella tela è raffigurato il martirio del Santo, che viene gettato in mare dentro un sacco pieno di serpenti. I laterali, che raffigurano i santi Giorgio e Lorenzo Giustiniani, sono opere giovanili del veronese Pasquale Ottino (eseguite fra il 1605 e il 1610 circa). Sul soffitto vi è dipinta una Gloria di San Giuliano, opera di Francesco Brici. Nella chiesa è anche conservato il sarcofago romano che conteneva le spoglie di San Giuliano prima del loro trasferimento, nel 1910, in un'urna posta sotto l'altare maggiore. La tradizione vorrebbe che il sarcofago, contenente le spoglie del Santo, sarebbe addirittura approdato sulla spiaggia di Rimini dalla Dalmazia o dalla Cilicia.