Born in Nalchik, Krasnozhan became the head coach of his native club Spartak Nalchik in 2004. In 2005, he managed to promote the modest club to the Russian Premier League. In spite of insufficient financing, the team avoided relegation, and nearly reached the Europa League places finishing in the 6th position in 2010. Following that season, Krasnozhan resigned to move to Lokomotiv Moscow.
On 4 June 2011, rumours spread that Lokomotiv chairman Olga Smorodskaya suspected Krasnozhan of throwing the home league game against FC Anzhi Makhachkala, played on 27 May and finished 1-2, and decided to fire him on the grounds of the suspicion. Lokomotiv was 5th in the table at that moment, just one point away from first-placed CSKA. On 6 July, after Lokomotiv Committee of Directors meeting, Krasnozhan's contract was officially terminated on the basis of "negligence in his job".Russian Football Union subsequently refused to investigate the case. On 27 December 2011, he was presented as Anzhi Makhachakala's head coach, on a 5 year deal. On 13 February 2012, before the team played a single official competitive game under his management, Krasnozhan was fired from Anzhi Makhachakala due to an unstable relationship with some players.
On 16 August 2012, he joined FC Kuban Krasnodar. On 8 January 2013, Krasnozhan was dismissed from his position after decision of the main investor.
On 26 May 2013, he was hired by FC Terek Grozny. He resigned on 28 October 2013 after Terek won only one game out of first 14 and was in 14th position in the table.