Faits:
A. A.a Par ordonnance pénale du 10 mai 2011, le Ministère public de l'arrondissement de Lausanne a reconnu X._ coupable de faux dans les certificats et infraction à la LEtr et l'a condamné à 75 jours de peine privative de liberté, sous déduction de 2 jours de détention provisoire. Sous la rubrique notification, l'ordonnance mentionne que X._, sans domicile connu, n'est pas avisé. L'ordonnance pénale lui a ainsi été notifiée sans publication officielle en application de l'art. 88 al. 4 CPP.
A.b X._ a formé opposition contre cette ordonnance pénale, le 24 août 2011. Par prononcé du même jour, le Président du Tribunal d'arrondissement de Lausanne a déclaré l'opposition irrecevable pour tardiveté.
B. Par arrêt du 5 octobre 2011, la Chambre des recours pénale du Tribunal cantonal vaudois a rejeté le recours de X._ contre le prononcé précité.
C. X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt, concluant, sous suite de dépens, principalement à sa réforme en ce sens que l'opposition formée contre l'ordonnance pénale est recevable, subsidiairement à son annulation. Il sollicite par ailleurs l'assistance judiciaire.
Le Ministère public conclut à l'admission du recours.

Considérant en droit:
1. Le recours en matière pénale au sens de l'<ref-law> est ouvert contre un arrêt de la Chambre des recours pénale vaudoise qui refuse de considérer comme recevable une opposition à une ordonnance pénale.
2. 2.1 Invoquant une violation des art. 29, 29a, 30 Cst., 6 CEDH et 14 Pacte ONU II, le recourant se plaint de n'avoir pas eu droit à un procès équitable. L'argumentation qu'il développe dans ce cadre se confond avec la violation de l'art. 88 CPP qu'il invoque également et n'a pas de portée plus étendue. L'examen portera sur cette seule disposition.
2.2 En bref, le recourant fait valoir que la fiction de notification de l'art. 88 al. 4 CPP ne peut lui être opposée et que le délai pour former opposition n'a effectivement pu commencer à courir que lorsqu'il a pris connaissance de l'ordonnance pénale du 10 mai 2011, soit le jour de son arrestation survenue le 24 août 2011.
3. 3.1 La notification d'une ordonnance pénale fait partir le délai d'opposition de 10 jours prévu à l'art. 354 al. 1 CPP. Le tribunal de première instance statue sur la validité de l'opposition (cf. art. 356 al. 2 CPP), en particulier le respect du délai de 10 jours.
Les art. 84 ss CPP régissent les formes de notification. L'art. 88 al. 1 CPP prévoit que la notification a lieu dans la Feuille officielle désignée par le canton ou la Confédération: lorsque le lieu de séjour du destinataire est inconnu et n'a pas pu être déterminé en dépit des recherches qui peuvent raisonnablement être exigées (let. a); lorsqu'une notification est impossible ou ne serait possible que moyennant des démarches disproportionnées (let. b); lorsqu'une partie ou son conseil n'a pas désigné un domicile de notification en Suisse, alors qu'ils ont leur domicile, leur résidence habituelle ou leur siège à l'étranger (let. c). Selon l'al. 4, les ordonnances de classement et les ordonnances pénales sont réputées notifiées même en l'absence d'une publication.
La fiction prévue par l'art. 88 al. 4 CPP est problématique. Selon le mécanisme de l'art. 88 CPP, elle n'est possible que si les conditions exigées par l'art. 88 al. 1 let. a, b ou c sont réalisées (cf. Message du Conseil fédéral, FF 2006 p. 1136 ad art. 86 al. 4 du projet; SARARARD ARQUINT, Basler Kommentar, Schweizerische Strafprozessordnung, 2011, n. 11 ad art. 88 CPP; DANIELA BRÜSCHWEILER, Kommentar zur StPO, Donatsch/Hansjakob/Lieber éditeurs, n. 8 ad art. 88 CPP). Il faut donc notamment que le lieu de séjour du prévenu n'ait pas pu être déterminé en dépit des recherches pouvant raisonnablement être exigées (cf. art. 88 al. 1 let. a CPP) ou que le prévenu sans domicile en Suisse n'ait pas désigné de domicile de notification en Suisse (cf. art. 88 al. 1 let. c CPP).
3.2 La Chambre des recours pénale a relevé qu'un prévenu doit s'attendre à recevoir une décision dès qu'il est informé de l'ouverture d'une procédure pénale. En l'espèce, le recourant avait été entendu par la police le 17 mars 2011, informé qu'une procédure préliminaire était ouverte à son encontre et avait signé l'avis comportant le passage suivant: "Si vous avez votre domicile ou résidence habituel à l'étranger, ou si vous n'avez pas de domicile fixe, vous êtes tenu(e) de désigner une personne en Suisse pour recevoir à votre place toutes correspondances, avis de procédure ou décisions concernant cette affaire (art. 87 al. 2 CPP). Si vous ne le faites pas, les décisions pourront vous être valablement notifiées par publication dans la Feuille des avis officiels (art. 88 al. 1 CPP); les ordonnances de classement et les ordonnances pénales sont réputées notifiées même en l'absence d'une publication (art. 88 al. 4 CPP)". La Chambre des recours pénale en a déduit que le recourant savait qu'il devait rester à disposition de la justice. Elle a exclu que le Ministère public ait insuffisamment cherché à localiser le recourant, celui-ci se trouvant en séjour illégal en Suisse et sans domicile connu au moment où l'ordonnance pénale a été rendue. En outre, elle a observé qu'il ressortait du procès-verbal d'audition du 17 mars 2011 que le recourant avait déclaré avoir été assisté par Me Christelle Pachoud (recte: Krystel Paschoud) et elle a nié que le Ministère public ait supposé que le recourant avait élu domicile auprès de Me Alain Brogli, cela même si ce dernier l'assistait dans une autre procédure pénale. Elle a ainsi considéré que le Ministère public pouvait notifier l'ordonnance pénale sans publication officielle et que c'était à juste titre que le tribunal de première instance avait déclaré irrecevable car tardive l'opposition à l'ordonnance pénale (cf. arrêt attaqué p. 4 et 5).
3.3 L'approche de la Chambre des recours pénale ne peut être suivie. Il ressort du procès-verbal précité que le recourant a déclaré ce qui suit: "J'ai un avocat en la personne de Me Christelle Pachoud [recte: Krystel Paschoud] mais renonce à ce qu'elle m'assiste pour cette audition". Or, d'après ce qu'indique le recourant dans son mémoire sans être contredit par le Ministère public, Me Krystel Paschoud était avocate stagiaire chez Me Alain Brogli, lequel le représentait également dans une autre procédure pénale. Il n'apparaît pourtant pas que le Ministère public aurait entrepris des démarches auprès de Me Paschoud ou de Me Brogli pour tenter de localiser le recourant. Le dossier ne permet d'ailleurs pas de percevoir quelle démarche le Ministère public a accomplie pour déterminer le lieu de séjour du recourant. Le Ministère public admet d'ailleurs dans ses déterminations qu'il n'aurait pas dû ignorer les déclarations du recourant. Il en résulte que les conditions légales n'étaient pas réunies pour appliquer l'art. 88 al. 4 CPP. L'arrêt attaqué viole par conséquent le droit fédéral.
3.4 Au vu de ce qui précède, il n'est pas nécessaire d'examiner plus avant si l'art. 88 al. 4 CPP est conciliable avec l'art. 6 CEDH (cf. art. 190 Cst.).
3.5 Le recours doit être admis et l'arrêt attaqué annulé, la cause étant renvoyée à l'autorité cantonale, qui se prononcera sur la validité de l'opposition en tenant compte de la connaissance effective par le recourant de l'ordonnance pénale.
4. Le recourant qui obtient gain de cause ne supporte pas de frais judiciaires (<ref-law>) et peut prétendre à une indemnité de dépens à la charge du canton de Vaud (art. 68 al. 1 et 2 LTF), ce qui rend sans objet sa requête d'assistance judiciaire.

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité cantonale pour nouvelle décision au sens des considérants.
2. La demande d'assistance judiciaire est sans objet.
3. Il n'est par perçu de frais judiciaires.
4. Une indemnité de 3'000 fr., à payer au conseil du recourant à titre de dépens, est mise à la charge du canton de Vaud.
5. Le présent arrêt est communiqué aux parties et au Tribunal cantonal du canton de Vaud, Chambre des recours pénale.
Lausanne, le 20 mars 2012
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Gehring