Somebody from Columbia Records gave her a nickname , `` Queen of the Blues '' . Soon , the press were calling her the `` Empress of the Blues '' . Columbia nicknamed her `` Queen of the Blues , '' but a PR-minded press soon upgraded her title to `` Empress '' .