По свидетельствам историков мусульмане населяли Петербург с самого его основания. Известно, что часть работ по обустройству Петропавловской крепости была произведена татарами. Неподалёку от Петропавловки, в районе нынешнего Кронверского проспекта, располагалась Татарская слобода. По неподтверждённым свидетельствам первое мусульманское кладбище было на Выборгской стороне, и было ликвидировано в связи с ростом города. Тогда у мусульман возникла необходимость получить место для нового кладбища. Прошение об устройстве такового было подано в 1798 году императору Павлу I, однако удовлетворено оно не было. Кладбище мусульманам было выделено много позже, в 1827 году императором Николаем I. Таким образом, именно Ново-волковское кладбище считается первым мусульманским в Санкт-Петербурге.
Территория была куплена мусульманами у деревенских жителей. Те охотно её продали, поскольку земля была непригодна ни для посевов, ни для сенокоса. Вероятно, место это было выбрано не случайно: кладбище здесь было и раньше: во времена русско-турецкой войны 1768—1774 гг., во время правления царицы Екатерины II, здесь хоронили пленных турок.
В исламе существуют два основных направления: суннизм и шиизм. Татары были суннитами. Сначала появилось татарское кладбище. Однако татары, сунниты, испытывали неприязнь к персам, шиитам, не желая видеть их могил на одной земле со своими. Поэтому персы ходатайствовали о выделении им отдельного участка. В1843 году он был выделен, но в обиходе оба кладбища по-прежнему именовали «татарским».
Изначально на Татарском кладбище планировалось хоронить высокопоставленных мусульман военных чинов, но позже стали хоронить и простых мусульман. Многие могилы были вовсе без памятников, никакого учёта не велось. О том, кто и где похоронен, знал только кладбищенский сторож. Происходило это, вероятно, по нескольким причинам. Во-первых, мусульманские традиционные похороны отличаются от христианских: тело предают земле непосредственно в день смерти, либо, если человек умер вечером, на следующее утро. Хоронят мусульмане без гробов, завернув покойного в саван. Брать плату за мусульманское погребение не считается возможным. Во-вторых, кладбище было бедным. Об этом свидетельствует тот факт, что, несмотря на требование закона огораживать кладбища заборами, тогдашний имам, высокопоставленное духовное лицо, в ведении которого кладбище находилось, не смог построить забор даже по прошествии трёх лет с момента открытия по причине отсутствия средств. Самые старые исторические захоронения относятся к середине 19 века. Это могилы персидского купца Ака Мухаммад Хаджи (ум. 1843) и Ака Мирза Садык (ум. 1844).
Эпидемия холеры в 1831 холера унесла множество жизней. На кладбище стали производиться массовые захоронения горожан, не имеющих отношение к исламу. Во время эпидемии здесь были похоронены многие известные в те времена люди: учёные, музыканты, придворные, деятели искусства. Например, создатель Павловского парка Пьетро Гонзаго, похоронен в 1831 году. На холерном участке была построена деревянная православная часовня, которая сгорела и не была восстановлена, хотя попытки и были.
В 1858 севернее холерного кладбища появилось магометанское. Оно единственное сохранило и до наших дней этническую целостность. На всех остальных участках со временем мусульманские захоронения смешались с прочими.
Через некоторое время на этом кладбище появился участок, где хоронили умерших без церковного покаяния, чаще, самоубийц. А во время русско-турецкой кампании (1877-1878) здесь хоронили умерших из Николаевского госпиталя, из низших чинов, тех, кому не хватило места на Православном Волковском кладбище.
Так кладбище действовало до 1871 года, после чего его закрыли. Но в годы Великой Отечественной Войны захоронения возобновились. Здесь находится братская могила умерших в блокаду ленинградцев. Выкопать что-либо в промёрзлой земле было невозможно. Сапёры закладывали взрывчатку, и в образовавшиеся траншеи складывали трупы, иногда в несколько слоёв. После чего их засыпали землёй, могилу прокатывали тяжёлой техникой и сверху выкладывали новый слой трупов. Это были и бойцы Ленинградского фронта и горожане.
Таким образом, собственно мусульманская часть кладбища, между рекой Волковкой и Волковским проспектом, совсем невелика. Большую часть территории занимают послевоенные захоронения. Здесь похоронены многие высокие военачальники, герои Советского Союза. В районе ул.Салова есть братская могила военных моряков и братская могила героев-железнодорожников, погибших в попытке предотвратить столкновение поездов, в их честь воздвигнута стела. В этом же районе кладбища похоронены многие деятели культуры и научной интеллигенции: автор первой книги о Дороге жизни, военный корреспондент, Ариф Сафаров (1912—1973); физик-оптик, доктор наук, Борис Ермаков (1934 – 1992); врач, профессор педиатрического институра, Юрий Котиков (1897—1979), театральный и киноактёр, Евгений Полосин (1912—1972).
В 1964 году из-за роста города кладбище было закрыто для массовых захоронений. Однако и сейчас Ново-Волковское кладбище сохраняет статус действующего. В наши дни здесь хоронят как по православному обряду, так и по мусульманскому.
Что касательно состояния кладбища, то всплывают печальные факты. В то время как ответственные службы докладывают о том, что кладбище содержится «в надлежащем состоянии», отзывы посетителей говорят об обратном. Были сообщения о появлении новых могил на том месте, где по проекту должна была быть дорожка, в результате чего посетители вынуждены «на карачках» пробираться между свежими могилами, чтобы пробраться к могилам своих близких. Известно так же, что во время весеннего паводка кладбище часто подвергается затоплениям, с которыми борется МЧС, в то время как проблема должна быть решена руководствам заблаговременно, путём своевременной осушительной мелиорации.
Реальный уход осуществляется за братскими могилами, видимо благодаря росту патриотизма в нашей стране в последнее время, в том числе силами школьников из окрестных школ, которые в преддверии праздника Победы выходят сюда на субботники.
Площадь современного Ново-Волковского кладбища составляет почти 33 га.