Charles’ Freund Britt Woodman war der Auslöser für einen weiteren Instrumentenwechsel. Britt spielte in einer Jazzband, die einen Bassspieler suchte und schlug daher Charles vor, doch zum Kontrabass zu wechseln. Was er dann auch in die Tat umsetzte. Fortan übte er wie schon zuvor, indem er mit den Bands aus dem Radio zusammenspielte. Im Alter von etwa 16 Jahren lernte Charles den Bassisten Red Callender kennen, der dann sein erster richtiger Bass-Lehrer wurde. Callender war schon ein recht bekannter Musiker und spielte mit Stars wie Louis Armstrong und später Nat King Cole. Zwischen Charles und Red entstand eine lebenslange Freundschaft.

Mingus übte täglich wie besessen, vertiefte seine musiktheoretischen Kenntnisse, lernte nebenbei das Klavierspiel und befasste sich mit dem Komponieren. Mit 17 Jahren verließ Charles Los Angeles und zog für einige Zeit nach San Francisco. Etwa zeitgleich veränderte sich der Sound des Duke Ellington Orchesters. Der Bassist Jimmy Blanton, hatte den Bass aus seiner untergeordneten Rolle befreit und rückte ihn stärker ins Zentrum des musikalischen Geschehens. Das gab wohl den Ausschlag für Charles’ Entscheidung auf einen Job Postangestellter zu verzichten und stattdessen Musiker zu werden.

Seinen ersten richtigen Job als Bassist erhielt Charles als Nachfolger von Red Callender, in der Band von Lester Young, dem großen Tenor Saxophonisten mit dem „Pok Pie Hat“. Im Jahr 1942 erhielt Charles die Chance mit Louis „Pops“ Armstrong eine Tournee durch die Südstaaten der USA zu machen, lehnte den karrierefördernden Job aber dankend ab. Charles war der Meinung, dass die Konflikte mit Armstrong vorprogrammiert sein, da er mit Louis’ „Onkel Tom-Allüren“ nicht so gut zurechtkommen würde. Charles’ Technik war mittlerweile so gut geworden, dass er problemlos jeden Job hätte annehmen können. Er hatte sich in der Swing-Szene zwar durchaus einen Namen gemacht, war aber unzufrieden mit sich und wollte sich als Instrumentalist weiterentwickeln. Red Callender empfiehl ihm den Bassunterricht von Hermann Rheinshagen, einem Musiker der New Yorker Philharmoniker, dessen „Classical Music Workshop Concerts“ Charles von nun an oft besuchte.

Im Januar 1944 heiratete Charles Mingus seine erste Frau Canilla Jeanne und wurde noch im selben Jahr Vater eines Sohnes. Um die Familie zu ernähren, arbeitete er als Studiomusiker und spielte nach Feierabend Sessions mit Dexter Gordon. Die Musik der Jahre 1944/45 schien Charles nicht besonders zu interessieren, was bemerkenswert ist, denn in diesem Jahr begann die Be Bop Revolution und Charlie Parker und Dizzy Gillespie waren in aller Munde. Es war keine gute Zeit für Mingus. Nach der Geburt seines zweiten Sohnes ging seine Ehe zu Bruch und Charles gerät, von Frau und Kindern verlassen, in eine tiefe Krise. Charles zieht sich zurück und nimmt einen Job bei der Post an.

Erst zwei Jahre später, im Jahr 1947, betrat Charles Mingus wieder die Musikszene und stieg in die Band des Drummers und Vibraphonisten Lionel Hampton ein. Hier schrieb Charles seinen ersten kleinen Hit: Mingus Fingers. Ähnlich wie beim möglichen Engagement bei Louis Armstrong, bekommt Charles auch schnell Probleme mit der Show seines Arbeitgebers Linonel Hampton. Dem Down Beat Jazz Magazin gegenüber bezog Charles Stellung:

„ Ich hoffe es wird nicht lange für einen Musiker nötig sein, auf dem Schlagzeug hin und her zu hüpfen, um auf sein Talent aufmerksam zu machen.“

Nach dem Engagement bei Lionel Hampton wurde Los Angeles erneut zum Zentrum der musikalischen Aktivitäten von Charles Mingus. Um seinen Unterhalt zu sichern, spielte er nun in den diversen Nightclubs sowie in der Big Band von Roy Porter. Die Arbeit in dieser Big Band war, im Gegensatz zu den Jobs in den Nightclub-Combos, für Charles sehr wichtig, denn hier lernte er einige der wichtigsten Musiker seiner späteren Karriere als Bandleader kennen. Neben dem Trompeter Art Farmer lernte Charles bei Roy Porter nämlich auch den Multi-Instrumentalisten Eric Dolphy und den Posaunisten Jimmy Knepper kennen. 1948 gibt Charles ein kurzes Gastspiel in der Band seines Freundes Red Callender und spielt in einigen Clubs in San Francisco. Die Erfolge bleiben jedoch aus und Charles muss wieder einmal als Briefträger bei der Post von Los Angeles arbeiten. Erst im Fruhjahr 1950 wird Charles wieder Profi-Musiker und übernimmt den Job des Bassisten in einem Trio von Red Norvo, einem musikalisch aufgeschlossenen Vibraphonisten, der zuvor mit Charlie Parker und Dizzy Gillespie gearbeitet hatte. Das spannende an diesem Trio (mit dem Gitarristen Tal Farlow) war die Tatsache, dass Norvo komplett auf einen Schlagzeuger verzichtete. Auch dieses vielversprechende Trio endete im Streit, nämlich just als Red Norvo Charles Mingus für eine TV-Sendung durch einen weißen Bassisten ersetzte.

Anfang des Jahres 1951 heiratete Charles Mingus seine zweite Frau Ceilia Nielson und spielte kurze Zeit in der Band des jungen Trompeters Miles Davis. Bei Miles lernte Charles den Pianisten Billy Taylor kennen, mit dem er zum Jahresende, unter der Leitung von Nat Hethoff, einige Trio-Aufnahmen sowie eine Rundfunksendung machte. Im Frühjahr 1952, Charles ist 30 Jahre alt, gründet er „Debut“, das erste „Independent Label“ der Geschichte und nimmt einige Titel mit dem Alt-Saxophonisten Lee Konitz auf. Neben einem Gastspiel im „Birdland“ mit dem Tenor-Saxophonisten Stan Getz kam es an gleicher Stelle auch zu einer Session mit Charlie „Bird“ Parker. Damit waren Charles’ Möglichkeiten, den Lebensunterhalt mit seiner Musik zu verdienen, für 1952 schon erschöpft und Charles jobbte wieder bei der Post.

Im Januar des Jahres 1953 wurde Charles’ Jugendtraum Wirklichkeit. Kein geringerer als sein großes Vorbild Duke Ellington machte Ihm ein Angebot. Nach einigen Rundfunkaufnahmen kam es leider auch in dieser Band zu Streitigkeiten zwischen Charles und einem Kollegen, was zu Folge hatte dass der Duke Charles die Kündigung nahelegte. So nahm Charles wieder ein Engagement im Birdland an. Diesmal mit dem legendären Be Bop-Pianisten Bud Powell. Im Mai jenes Jahres kam es dann zum Treffen der Giganten. Das Bud Powell Trio spielte mit Mingus in der Massey Hall in Toronto. Nach dem Set des Trios wurde dieses durch Dizzy Gillespie und Charlie Parker komplettiert und es wurde Musikgeschichte geschrieben. Der genesene Parker war bestens Aufgelegt und auch die anderen Musiker standen Ihm in nichts nach. Dank Charles’ Debut Records wurde dieses Ereignis konserviert und zählt zu den besten Bop-Aufnahmen der 50er Jahre.