Хож-Ахмед родился 11 ноября 1954 года в Киргизии. Его семья, в числе других чеченских семей, в 1944 году была выслана в Среднюю Азию (многие чеченцы во время войны сотрудничали с немцами). В 1957 году советское правительство отменило наказание чеченцам, и Нухаевы вернулись в Чечню, в Грозный.

В своей официальной биографии Хожа Нухаев сообщает, что появился в Москве в 1974 году. По его словам, он поступил на юридический факультет МГУ, хотя диплома так и не получил. В 1980-е Нухаев стал одним из главарей чеченской общины (чеченской мафии) в Москве. Несколько раз сидел.

Освободившись в последний раз из тюрьмы, в 1991 году, Нухаев занялся политикой, приблизился к чеченскому президенту Джохару Дудаеву, проводил подпольные финансовые операции для общака независимой Ичкерии. В 1994 году, когда федеральные войска вошли в Чечню, Хожа принял участие в обороне Грозного. В январе 1995-го был ранен в боях за президентский дворец — он до сих пор хромает и ходит с палкой. После лечения в Турции занял пост первого заместителя премьер-министра при Земилхане Яндербиеве. В начале 1997 года политическая ситуация в Чечне изменилась не в пользу Нухаева. Президентом Чечни был избран Аслан Масхадов, который назначил своим премьер-министром известного полевого командира Шамиля Басаева. Нухаев решил уехать — жил то в Стамбуле, то в Баку, где у него были банковские счета и свои дома. Занялся какими-то нелепыми экономическими проектами (под названием «Кавказский общий рынок»), открыл представительства в Киеве, Варшаве, Брюсселе, Лондоне, Вашингтоне, Хьюстоне и Токио. Идея была заманчива: создать Общий рынок независимых народов Кавказа и подключить его к мировой экономике. Проповедуя эту идею, а также экономическую независимость Чечни, Нухаев в 1997 году встречался с Маргарет Тэтчер, с бывшим секретарем безопасности США Збигневом Бжезинским, с бывшим госсекретарем США Джеймсом Бейкером, председателем Всемирного банка Джеймсом Вульфенсоном. Экспертный совет организации «Кавказский общий рынок» возглавил первый президент Европейского банка реконструкции и развития Жак Аттали.

Однако ничего из этого проекта не получилось — по крайней мере в экономическом смысле. Нухаев увлекся богословием и философией, стал исламским фундаменталистом и приверженцем «нового евразийства».

База Нухаева в Баку была расположена в гостинице «Абшерон». Это огромное пустующее здание в самом центре города превратилось в логово чеченских сепаратистов. Нухаев разъезжал на бронированном шестисотом «мерседесе», но другой роскоши, по-видимому, себе не позволял. Ходил всегда в одном и том же элегантном сером костюме (какого-то неопределенного евразийского стиля) и строго соблюдал мусульманские обряды. В офисе Нухаева висели портрет Дудаева, чеченский флаг и шашка, в углу стояла винтовка XIX века, было полно книг — исламское богословие, русская и немецкая философия.