Levein led the national team to just two points from their opening four World Cup qualifying games and subsequently paid the price earlier in November.
But Miller believes that the former Dundee United manager was badly let down by his charges and says that he enjoyed working under his guidance.
"A few of us have come out and said we felt we let the manager down with the performances in the first four games," he told the BBC.
|10/1||Owen Coyle is 10/1 with Bet365 to be the next permanent Scotland manager
"We did genuinely feel that the right man was at the helm. Me personally, I was as optimistic as ever going into this group thinking we've got a good team here and it's a group where I think a lot of teams will take points off one another.
"We felt we had everything in place to go and have a right good campaign. The squad was there, the spirit was there, there was a great atmosphere within the players and the coaches.
"Unfortunately, we have not gone out and got the results that would allow that to continue but, in football, these things happen. You've got to move and we've got a job to do now.
"After our poor start to the campaign, we've got two games, one now and one in February, to hopefully get a bit of confidence going into the qualifiers in March.”
The 32-year-old expects plenty of young players to be handed the opportunity to impress when Under-21s manager Billy Stark takes temporary charge for Wednesday's friendly clash with Luxembourg.
"It is the usual friendly date in November, but obviously, with the call-offs, it gives younger lads who are maybe on the fringes and doing very well at their clubs to make a stake for a place in the squad," he added.
"With Billy coming in as well, it's a new-look squad, a new-look team are taking the squad and I think it is important first and foremost that we win the game.
"There's always call-offs in the national set-up, particularly for friendlies, when you look at the lads who are playing Champions League and playing midweek games and weekends and people needing a bit of a rest."
|"We're disappointed because we enjoyed working with Craig ... We did genuinely feel that the right man was at the helm"
- Kenny Miller on Craig Levein
Miller went on to back former Celtic coach Gordon Strachan to take up the Scotland managerial role on a permanent basis.
"Gordon has done a great job at many of the clubs he's been at, none more so than Celtic," he continued.
"He's obviously been tipped as favourite for the job and I'm sure he's very passionate about the national team, he's been capped many times as a player and I'm sure it's a role he would welcome."