Графская пристань была построена 31 июля 1783 году за месяц с небольшим из тесанного камня с деревянным шлюпочным причалом. 

                В 1787 году к приезду в Севастополь Екатерины II, по указу князя Потёмкина пристани присвоено название Екатерининская, но официальное название у
севастопольцев не прижилось. 
                В то время главным командиром черноморского флота был граф, контрадмирал Марко Иванович Войнович. Каждое утро по традиции он спускался по пристани к шлюпке для ежедневного осмотра кораблей и эта красивая традиция привлекала к себе толпы народа.
В момент, когда он проходил к шлюпке в толпе раздавалось: «Смотрите, смотрите, граф идёт!» Так и стала пристань Графской…
Всем известный вид пристань приобрела в 1846 году – эта дата выбита на аттике. В 1846 году по проекту инженер-полковника Джона Уптона, утвержденному в октябре 1844 года, была построена новая пристань, как парадный вход в Севастополь со стороны моря.