Роботу в органах внутрішніх справ розпочав у червні 1984 року.

Перша посада в міліції – міліціонер відділення внутрішніх справ на станції «Христинівка» відділу внутрішніх справ на станції імені Т. Г. Шевченка Південно-Українського управління внутрішніх справ на транспорті. 

Із липня 1984 року до серпня 1988 року працював на різних посадах на станціях Південно-Українського управління внутрішніх справ на транспорті. 

Після навчання у Київській вищій школі МВС СРСР у 1991 році працював старшим інспектором профілактики Ленінського райвідділу внутрішніх справ УВС міста Києва, згодом – старшим інспектором відділу з керівництва дільничними інспекторами міліції Старокиївського районного відділу внутрішніх справ УВС міста Києва. 

У березні 1993 року призначений інспектором відділення з організації бойової підготовки відділу професійної підготовки управління кадрів ГУВС міста, а в квітні 1993 року – начальником інспекції у справах неповнолітніх Старокиївського районного відділу внутрішніх справ УВС міста Києва. 

Із вересня 1994 до вересня 1995 року був слухачем факультету підготовки керівних кадрів Української академії внутрішніх справ.

Із вересня 1995 року працював у Головному управлінні МВС України в місті Києві на старшим інспектором інспекції у справах неповнолітніх управління карного розшуку, старшим оперуповноваженим в особливо важливих справах відділу кримінальної міліції у справах неповнолітніх, заступником начальника відділу професійної підготовки – начальником відділення організації бойової підготовки управління по роботі з особовим складом, заступником начальника відділу професійної підготовки управління роботи з особовим складом, заступником начальника управління роботи з персоналом – начальником відділу професійної підготовки.

У травні 2003 року призначений заступником Голови Державної податкової адміністрації у місті Києві. 

Із січня 2005 до жовтня 2005 року обіймав посаду проректора щодо роботи з персоналом – начальника відділу роботи з персоналом Київського юридичного інституту МВС України.

У жовтні 2005 до січеня  2008 року працював начальником Печерського районного управління Головного управління МВС України в місті Києві. 

Із березня 2008 року до березня 2010 року був заступником начальника Головного управління МВС України в місті Києві – начальником управління кадрового забезпечення.

З березня 2010 року до червня 2012 року працював начальником Голосіївського районного управління Головного управління МВС України в місті Києві.

З червня 2012 до листопада 2012 року обіймав посаду начальника управління боротьби з незаконним обігом наркотиків МВС України.

17 листопада 2012 року очолив Управління МВС України у Волинській області. 

25 лютого 2014 року написав рапорт про відставку.

З 22 липня 2014 року — Начальник Головного Управління МВС України у місті Києві. 5 червня 2015 року був звільнений з посади.

3 липня президент України Петро Порошенко скасував люстрацію Олександра Терещука.

14 грудня 2015 року Міністр МВС України Арсен Аваков повідомив, що звільнив начальника Головного управління Національної поліції в Києві Олександра Терещука і декількох високопоставлених співробітників столичного главку.

Відзначений багатьма відомчими нагородами.