Родился под Новосибирском. Греко-римской (классической) борьбой начал заниматься в секции Новосибирского электротехнического института с 1981 г. Однако на этом его спортивные интересы не закончились.

Мальчик любил охотиться, бегать на лыжах и плавать. Его первым и единственным наставником был и остается до настоящего времени заслуженный тренер СССР В. М. Кузнецов.

В 1986 г. Карелин потерпел единственное поражение - уступил чемпиону мира Игорю Растороцкому. Но уже через год спортсмен стал чемпионом мира среди юношей и попал в состав главной сборной страны.

На Олимпиаду в Сеул (1988) Карелин поехал благодаря тому, что выиграл схватку с двукратным чемпионом мира Игорем Растороцким. Дебютант выступил блестяще, завоевав золотую медаль.

Через четыре года в олимпийской Барселоне спортсмен вновь доказал свою непобедимость в греко-римской борьбе. Четыре из пяти поединков он завершил досрочно: за 1,5 минуты одержал верх над канадцем Эндрю Бордоу, за 2 минуты одолел кубинца Россела Меса, за 15 секунд - румына Иона Григораша.

В финале Карелин продемонстрировал свой высокий профессионализм и несокрушимую силу чемпиону мира, двадцатикратному чемпиону Швеции Томасу Юханссону. Зарубежный спортсмен продержался не более 2 минут.

В 1989 г. Александр пятый раз подряд завоевал титул чемпиона мира. Позднее журналисты выяснили, что практически на протяжении всего чемпионата спортсмен выходил на ковер со сломанным ребром.

В 1996 г. в Будапеште на чемпионате Европы он также выступал с травмой (в поединке с белорусским борцом оторвалась грудная мышца), но у него и мысли не возникло снять свою кандидатуру с соревнований. Здоровье Карелина было подорвано; врачи настойчиво рекомендовали ему не принимать участия в Олимпиаде в Атланте.

Но переубедить кому-либо самого сильного борца планеты оказалось не под силу. Остаться в стороне от бурной олимпийской жизни и подвести свою команду Александр не мог.

Наградой за силу воли спортсмену стал победный гимн, прозвучавший в его честь в олимпийской Атланте (1996). В этом же году Александру Карелину вручили "Золотую Звезду" Героя России.

После Олимпийских игр в Сиднее (2000), где спортсмен стал серебряным призером, он принял решение уйти из большого спорта.

В настоящее время активно занимается политической деятельностью.