臧霸在後世的名聲可能不太大，那是因爲種種的緣故，然於當下而言之，他卻是一個赫赫有名的“豪俠”，——荀貞早在爲繁陽亭長時就知聞過他的名字，當時荀貞到繁陽亭上任，在繁陽亭亭舍的板壁上見到了一道朝廷通緝他的文書。
臧霸小名奴寇，字宣高，泰山郡華縣人，生於延熹八年，今年才二十五歲，年紀很輕，年紀雖輕，卻已是一個被朝廷通緝多年的“要犯”了。
他被朝廷通緝的那一年，他才十八歲。
那一年，他時爲華縣獄掾的父親藏戒因爲據守法律，不肯配合郡守殺人，從而引得郡守大怒，惹禍上身，結果被郡吏收捕、押往郡府。臧氏在華縣、乃至在泰山郡都是個大姓，在當地很有勢力，爲了能夠保證順順利利地把藏戒押到郡府，郡守當時調集了百餘甲士。
臧霸時在家中，驚聞此事，當機立斷，馬上召集家中門客數十人，抄小路趕到了這支押送人馬的前邊，在費縣西山這個地方截住了他們。
截住了之後，他就上去搶人。他時年方纔十八，古人計年齡是從胎兒始，也就是說，十月孕滿，生下來便是一歲，亦即是說，臧霸這一年按後世的計齡實際上才十七歲，年僅十七，身邊又只有數十門客，而對面是百餘甲士，怎麼看他的勝算都不大，可是他的氣勢卻十足，竟壓制了對面的這百餘甲士，那百餘甲士無人敢動，眼睜睜地看着他把他的父親給搶走了。
經此一事，臧霸遂以“孝烈勇壯”而聞名鄉野。
朝廷通緝他後，天下亭舍皆高懸其名、高懸其事，又等於是變相地給他揚名，於是，他的名聲就不但是聞於鄉野，現如今更是天下知之了。
卻說搶走了父親之後，臧霸便與他父親、數十門客一起從泰山郡逃到了徐州的東海郡。
東海是徐州五郡之一。徐州最北邊是琅琊郡，琅琊郡南邊就是東海郡，東海、琅琊此二郡皆與兗州的泰山郡接壤。臧霸和他父親是泰山人，雖然說起來和東海、琅琊分屬二州，可因爲接壤之故，他們父子對東海、琅琊也是很熟的。
到了東海郡後，按理說，這不是他們的地盤，他們就算對這裏再熟，卻也是個外來者，通常情況下，朝廷應該很容易就抓住他們纔對，卻又是爲何多年捕之不得？
這不是地方郡縣、亭舍的執法能力不行。
總的來說，大約是因兩個緣故。
其一，隨着朝廷的通緝文書傳播，臧霸“孝烈勇壯”的名聲越來越大，名聲一大，自然就會引起名豪大俠們的注意。“隱匿亡命”雖是重罪，但卻一直以來都是名豪大俠們常乾的事兒，尋常的亡命之輩，名豪大俠們尚且隱匿，何況臧霸這樣的“年少英雄”？
於是之，東海，甚至東海周邊各郡的名豪大俠無不爭相邀請，以搶着能把他父子請到自己家裏“隱匿”居住爲榮。
這些名豪大俠都是當地的地頭蛇，有他們護着，郡、縣、鄉、亭就算知道臧霸在哪兒，他們也不敢去抓，——上頭下令的可能是外來的長吏，底下的辦事可都是本地人，誰會傻乎乎地爲了一個外來的長吏而去得罪本地的大豪？
——不僅臧霸，事實上，這種情況在兩漢是非常流行的，遠的不說，只說荀貞身邊的人，許仲、典韋兩個便不都是和臧霸一樣，受了通緝多年，不僅若無其事，反而名聲愈振。
這是一個緣故。
再一個緣故，東海歸徐州所屬，不歸兗州。
臧霸搶走了他的父親，泰山郡的時任郡守當然非常惱怒，可東海不歸他管，即使他上書州府，東海也同樣不歸兗州監，這麼一來，這個郡守便是再惱怒，卻也是無可奈何。
以是之故，臧霸和他的父親亡命多年，卻不但沒有被抓住，反而名頭變得越來越大。
陶謙家在丹陽郡，丹陽郡在徐州南邊，與廣陵郡接壤，離東海、泰山都不是太遠，所以他早在來徐州之前就久聞臧霸之名了，知道這個人雖然年輕，卻是個當之無愧的英傑，因此，去年一到徐州，他就親自派人去東海郡把臧霸給請了來，——從這一點卻也可以看出，臧霸在東海郡這件事可以說幾乎已經是光明正大的了，知道他在這兒，可朝廷就是抓不了他歸案，由此亦可看出他的名頭之大、可以看出他在兗、徐豪俠中的人望。
陶謙此前曾以“參軍事”的身份跟着張溫擊邊章、韓遂，雖然說他是張溫特地請去的，張溫待他也很高看、親厚，可他因爲看不起張溫的行事方法，卻對張溫很不客氣，有次在酒宴上，張溫叫他起來行酒，他不幹，藉着酒勁在席上公然羞辱張溫。張溫再好脾氣也受不了下吏當衆辱己，非常生氣，決定治他的罪，把他徙邊，後來因別人之勸而改變了主意，又派人去把陶謙給追了回來。陶謙回來後，勸張溫改變主意的那人又來勸他，叫他態度好點，陶謙當時答應了。可是，在見到張溫後，陶謙卻揚着臉，不看張溫，說：“我有罪，我當向天子請罪，和你有什麼關係？”要說張溫這個人能力可能不足，但脾氣真是不錯，見陶謙還是這態度，卻沒有再生氣，而是笑道：“恭祖，你的癡病還沒除的麼？”給陶謙置酒，待之如初。
張溫的這一句“恭祖癡病尚未除邪”？固然是大度之辭，卻也是無可奈何之語。
可見，陶謙這個人也是有點恃才自傲，有點尚氣輕死的任俠習氣，有點“小爆脾氣”的。
他和臧霸卻倒是因此而脾氣相投。
兩人“君臣投契”，以陶謙帶來的丹陽兵和臧霸募召來的泰山兵爲基礎，加上徐州本地勢力的配合，三方合力並戰，卻是一戰而便大破徐州黃巾。
戰罷，陶謙遂舉臧霸爲騎都尉，同時舉孫觀爲騎都尉。
臧霸聞名海內這麼多年了，徐州、尤其是他家鄉兗州泰山的豪傑們很多都與他有來往，乃至投到了他的門下，孫觀便是與他來往甚密的一個。
除了孫觀，臧霸身邊有名的豪俠還有吳敦、尹禮、昌豨以及孫觀的兄長孫康等人。
這幾個人，就是臧霸麾下泰山兵的各部主要首領。
臧霸麾下的這支泰山兵並不是純由泰山人組成的，也有東海
人、也有琅琊人、也有別的郡的人，不過其主幹是泰山人，各部的首領如孫觀等人也多是泰山人，所以現在的徐州上下，上至州府、下到黔首，都以“泰山兵”稱呼他們。
他們這支人馬，儘管臧霸、孫觀現而今各有了一個“騎都尉”的武職，可嚴格來說，既不是徐州的州兵，也不是朝廷的官軍，實際上是等同“義從部曲”、“僱傭兵”性質的。