Отец композитора был внебрачным сыном генерала А. Селиверстова и пленной турчанки, получившим усечённую фамилию, однако был приписан к дворянскому сословию как выходец из польского шляхетства. Мать, Анна Васильевна (урождённая Волкова), происходила из военной среды.
С детства был приобщён к музыке, поскольку отец содержал крепостной оркестр и устраивал домашние музыкальные собрания. Вместе со своим братом Василием и сестрой Варварой обучался игре на скрипке и фортепиано. С девяти лет выступал в концертах в Уфе.
В 1816 переехал в Санкт-Петербург. Там был определён в Институт корпуса инженеров путей сообщения, где проучился один год, после чего поступил на службу и до 1823 года служил в разных учреждениях. Тем временем продолжал своё музыкальное образование, брал уроки у Дж. Фильда и Д. Штейбельта (фортепиано), Тарквини (пение), Ф. Бёма и Л. Маурера (скрипка), Брандта, К. Цейнера, Миллера (теория композиции). В эти же годы начал увлекаться театром (среди его петербургских друзей были выдающиеся деятели театра: князь А. А. Шаховской, П. Н. Арапов, А. А. Алябьев, Н. В. Всеволожский, П. Е. Мансуров, Ф. Ф. Юрьев). Активно участвовал в любительских спектаклях в качестве переводчика пьес, актёра, певца и автора музыки к театральным постановкам.
Его первые три оперы-водевили «Бабушкины попугаи» (1819), «Карантин» (1820), «Новая шалость, или Театральное сражение» (1822) были поставлены в Петербурге и имели успех. Тексты этих произведений создал друг А. Верстовского, популярный в то время в Петербурге драматург Н. И. Хмельницкий.
С 1823 года до конца жизни жил в Москве. Поначалу был переведён в Москву чиновником особых поручений канцелярии при генерал-губернаторе Д. В. Голицыне, затем в контору Дирекции императорских театров. С 1825 занимал должность инспектора музыки Дирекции московских театров, с 1830 — инспектора репертуара, а с 1842 по 1859 он был управляющим Московской театральной конторой.
После долгих лет жизни в наёмных домах с супругой, известной актрисой и певицей Н. В. Репиной, в 1836 они купили собственный домик на Арбате (в Большом Афанасьевском переулке № 16/24), где жили до переезда в Хлебный переулок в 1860 (дом был снесён в 1971 году). Здесь их посещали Ф. Лист (в 1843 г.), Р. Шуман со своей женой Кларой (в 1844 г.) и, вероятно, в 1847 г. Г. Берлиоз.
Был фактическим руководителем театральной жизни города. Показал себя не только энергичным администратором и умелым руководителем, но и часто выступал в роли режиссёра и педагога. Всячески способствовал обогащению репертуара, улучшению работы театральной школы, поднятию художественного уровня спектаклей, уделял большое внимание подбору и воспитанию актёров. Его стараниями при Дирекции московских театров были открыты музыкальные классы, готовившие оркестрантов для будущей работы в театральных оркестрах. В 1826 совместно с А. И. Писаревым издавал «Драматический альбом для любителей театра и музыки» (вышло 2 книги). В 1829 стал членом Общества любителей русской словесности. В 1833 экстерном закончил Императорский Московский университет.
Автор преимущественно музыкально-сценических произведений — опер и опер-водевилей, а также баллад. Создал 6 опер — «Пан Твардовский» (1828), «Вадим, или Пробуждение двенадцати спящих дев» (1832), «Громобой» (1854, постановка 1857) и другие. Лучшей считается «Аскольдова могила» (1835) по роману М. Н. Загоскина, пользовавшаяся большой популярностью. Необычайно стойкий успех его лучшей оперы отмечал выдающийся критик А. Серов. В 1862 г., после смерти композитора, он писал, что «в отношении популярности Верстовский пересиливает Глинку».
Также прославился романсами — «Слыхали ль вы за рощей глас ночной», «Старый муж, грозный муж» (на стихи А. С. Пушкина; последний «цыганский романс» неоднократно исполняла П. Виардо-Гарсиа), кантатами, духовной музыкой. В русской вокальной лирике создал новый жанр — балладу, или «драматические кантаты», как он сам называл такие сочинения. Это повествовательно-драматические произведения для солиста с инструментальным сопровождением, написанные в свободной форме. К лучшим балладам относят «Чёрная шаль» (на стихи А. С. Пушкина), «Бедный певец» и «Ночной смотр» (на стихи В. А. Жуковского), «Три песни скальда» и другие.
