Niestety wskutek braku funduszy w 1941 musiał zrezygnować z nauki i przez pół roku jeździł z koncertami, występując w orkiestrze uniwersyteckiej stanu Kansas. Następnie przeniósł się do Kansas City w Missouri, gdzie występował w klubach, doskonaląc swój oryginalny styl, który nawiązywał do gitarowych rozwiązań Christiana i zawierał elementy muzyki country. Po przystąpieniu Stanów Zjednoczonych do wojny chciał wstąpić do wojska, ale został odrzucony ze względu na wykryte u niego szmery serca.
W 1943 zaangażował się do popularnej orkiestry tanecznej, Casa Loma, prowadzonej wówczas przez saksofonistę Glena Graya. Dzięki temu został zauważony przez czasopisma jazzowe, które pochlebnie recenzowały grę młodego gitarzysty. W latach 1945–1947 pracował w big-bandzie Jimmy’ego Dorseya. W orkiestrze Dorseya grał także jego kolega z Casa Loma, pianista Lou Carter oraz kontrabasista i skrzypek, Johnny Frigo. Dzięki temu ostatniemu nastąpił zwrot w karierze Ellisa, który znacząco wpłynął na jej dalszy przebieg.