В двенадцать лет был отдан в Киевский частный немецкий пансион.
В 1821 году поступил в Благородный пансион при Петербургском университете, который окончил в 1824 году с высшей наградой, правом на чин X класса.
Поступил на службу секретарем при директоре почтового департамента.
В 1831 году был переведен в Одессу, получив место помощника начальника VII почтового округа Новороссийского края. Перед ним открылась блестящая служебная карьера. В 1850 году вышел в отставку (в чине действительного статского советника и со званием камергера). Поселившись в отцовском имении «Ярославка», он предался хозяйственной деятельности, занимался садоводством, серьезно увлекался ботаникой.
В 1838 году женился по любви на дочери крупного херсонского помещика Марии Сергеевне Кудашовой. Счастливый в браке, Андрей Подолинский был несчастлив в детях: одного сына потерял ребенком, другого еще в молодые годы поразил тяжелый недуг, перешедший затем в прогрессивный паралич. Трагическая судьба и ранняя гибель сына омрачили старость Подолинского.
Последние годы жизни провел в Киеве.
Случайная встреча семнадцатилетнего Подолинского с Пушкиным в Чернигове в 1824 году (о ней он впоследствии рассказал в своих воспоминаниях) (Русская старина.— 1885.— № 1. — С. 77) была воспринята им как перст судьбы. Подолинский решился вступить на литературное поприще.
Выступил в печати в 1827 году с поэмой «Див и Пери».
Сблизившись с кругом А.А. Дельвига, много печатался в альманахах. Однако после отрицательного отзыва о поэме «Нищий» (1830) в «Литературной газете» порвал с литературными друзьями.
В 1837 году вышли «Повести и мелкие стихотворения» (в двух частях) Подолинского, после чего участие его в литературной жизни почти прекратилось. Второе издание стихотворений (1860) было недоброжелательно встречено шестидесятниками, воспринявшими его творчество как анахронизм.
В 1885 году в журнале «Русская старина» (№ 1) опубликовал цикл стихотворений.
Стихотворения «Жребий», «Вечер», «На развалинах Десятинной церкви в Киеве», «Природа», «Под необъятным сводом неба», «Мелодия» и др. являются вкладом поэта в сокровищницу русской поэзии.
Сын — учёный-энциклопедист Сергей Подолинский.
Умер Андрей Подолинский 16 января 1886 года (4-го по ст. ст.) в Киеве, похоронен на кладбище Аскольдовой могилы. В 1930-х годах прах отца и сына Подолинских был перенесен на Зверинецкое кладбище.
Посмертно напечатаны прозаическая повесть «Змей» (там же, 1886, кн. 7) и воспоминания («Русский архив», 1872).

На развалинах Десятинной церкви в Киеве

Зачем тревожить сон гробов,
Могил священное молчанье,
И поверять бытописанье,
Стряхая с камней пыль веков?
Все та же истина: от века
Иной нам опыт не открыл,
Мы видим — крепостъ высших сил
И всю ничтожность человека!
А время? — кто его сочтет?
Оно до нас существовало;
Исчезнем мы — оно сольет
С своим концем свое начало,
Как на граните гробовом
Змея, согнутая кольцом!

Биобиблиографическая справка
Собрание сочинений
Википедия