Андрей Матвеевич Байков происходил из петербургского дворянского рода. Родился он в Харькове 17 сентября 1831 года. Окончил Императорское училище правоведения с золотой медалью, и в мае 1850 года поступил в Департамент юстиции. Отличился в Крымской войне: «1 июня 1854 г., будучи послан на остров Равенсари с дружиной ратников, он участвовал в деле против неприятелей во время бомбардирования острова английским флотом, и ранен».
В 1862 году А.М. Байков стал городским головой Ростова-на-Дону, а спустя четыре года был избран на второй срок подряд. За эти два срока в Ростове получило распространение керосиновое освещение, появился водопровод, были учреждены Биржевой комитет, городской общественный банк, Ростовское-на-Дону общество взаимного кредита, городские отделения Государственного банка и Коммерческого Совета. На средства А.М. Байкова была сооружена кладбищенская церковь во имя Всех Святых. Ему же город обязан появлением первой газеты («Ростовские-на-Дону городские ведомости») и первого постоянно действующего театра. Наконец, в период его первого правления в городе появились Общество взаимного вспоможения приказчиков, Александровское благотворительное общество, Петропавловская богадельня.
Значительную роль сыграл Андрей Матвеевич и в создании Ростовского водопровода. В 1860 году он, совместно с купцом Михалевым и Белелюбским, создал «Акционерное общество Ростовскаго на Дону водопровода». Однако акции общества раскупались плохо, и в январе 1864 года «учредители общества уведомили городскую думу, что общество не состоялось, "а потому, если угодно будет городскому обществу передать устройство водопровода другим лицам, то на это препятствий не будет"». «Другими лицами» оказались торговый казак С.Н. Кошкин, ейский купец 1-й гильдии Г.В. Дмитриев и ростовский купец 2-й гильдии Т.П. Кукса. Им была отдана концессия на сооружение водопровода сроком на 50 лет, и уже «24 декабря 1865 года вода поднята и пущена по городу из устроенного резервуара».
Во второй половине 1860-х годов А.М. Байков возглавил Комитет донских гирл, созданный в 1865 году при его активном участии. Андрей Матвеевич был первым председателем комитета, и по его инициативе в 1866 – 1867 годах контр-адмирал П.Е. Белявский провел исследование донских гирл.
Важным достижением А.М. Байкова можно считать изменение положения мещанского сословия и отношения к его представителям. До прихода Андрея Матвеевича на пост городского головы купцы монополизировали право на управление городом и всеми сферами общественной жизни. Мещанский староста Ростова Н.И. Бочаров так описывал эту ситуацию: «мещанин был словом почти бранным; нас брали, таскали, садили без вины, отпускали без суда». Но в результате действий А.М. Байкова, по словам того же Н.И. Бочарова, «мещанин сделался человеком. Вы протянули ему руку, а за Вами и другие перестали считать его зараженным проказою. Мещанин сделался равноправным с другими гражданами… Земледельцы при Вас ограждены от влияния монополистов открытием кредита для мещан в общественном банке; Вы дали мещанам широкие средства развить свою торговлю и улучшить свое состояние».
В 1869 году А.М. Байков был вынужден оставить пост городского головы в связи с обвинениями в злоупотреблениях. По мнению ряда влиятельных лиц (в частности, доктора медицины Г.И. Ткачева, занимавшего видное положение в ростовском обществе), А.М. Байков брал из городского общественного банка (по сути, из городского бюджета) деньги на личные нужды. Обвинение доказано не было, но Андрей Матвеевич не счел возможным продолжать работу в условиях подобных нападок.
«21 августа 1871 года Байков был причислен к Главному управлению наместника на Кавказе и получил еще одного "Станислава с императорской короной". Вслед за чем назначен почетным мировым судьей Владикавказа и вновь стал заведовать Кавказскими минеральными водами».
Вернулся А.М. Байков в Ростов в 1884 году, по настоятельной просьбе ряда представителей ростовской элиты. И сразу занял пост городского головы, а вскоре повторно возглавил и Комитет донских гирл. Второе его пребывание у власти заметно повлияло на жизнь Ростова-на-Дону. «Для заведования хозяйственною частью городских начальных училищ был учрежден в 1884 г. попечительный комитет». В 1886 году в Ростове появился телефон, а на следующий год была введена в эксплуатацию конно-железная дорога. Также в 1887 году была создана санитарная лаборатория при ростовской больнице.
А.М. Байков был последовательным сторонником идеи сооружения Волго-Донского канала. В середине 1880-х годов ростовские предприниматели выступили с инициативой создания «Франко-Русского частного общества изысканий и составления проекта Волго-Донского канала». Учредителями товарищества стали 18 ростовчан и 18 парижан. Среди учредителей, помимо А.М. Байкова, были такие известные ростовские деятели, как П.Р. Максимов, А.Л. Мордовцев, Ф.Н. Солодов, В.И. Асмолов, Н.А. Панин, Н.И. Чурилин, Г.И. Шушпанов, Я.С. Кушнарев, И.С. Леванидов. Результатом деятельности товарищества стал ряд проектов канала, однако, ввиду нерешенности вопроса о финансировании работ, ни один из этих проектов не был реализован.
А.М. Байков скончался в австрийском городе Меран (где он находился на лечении) 18 сентября 1889 года.