A ocupação e povoação da região começou entre os séculos XIII e XIV por inciativa de um homem chamado Mecau (ou M'nkau), príncipe do reino Quinara. Em busca de locais de caça príncipe Mecau descobriu a ilha de Bissau, território que o agradou muito por parecer área fértil e propícia à caça. Mecau voltou ao seu reino, despediu-se de seu pai, e partiu com suas seis esposas para a ilha. inclusive trazendo sua irmã grávida, formando tanto o grupo étnico papel, como o Reino de Bissau. Da irmã de Mecau, a princesa Pungenhum, nasceu Itchassu, descendente que formou o clã dos bôssassum (ou bissassu-nanque-ié), que eram os reis, fidalgos e nobres entre os povos papéis.

Mecau foi o primeiro soberano do reino de Bissau, passando sua autoridade real a Itchassu (ou Bôssassu), o seu sobrinho. Nos primeiros anos o reino pareceu ter forte contacto político, econômico e religioso com os beafadas, a etnia do reino Quinara. Havia também contactos da mesma natureza com os manjacos e brames-mancanhas, povos que inclusive têm afinidade linguística com os papéis.A princípio todos os aldeamentos estavam sob a autoridade do reino de Bissau, contudo as diversas lutas pela sucessão do trono fizeram com que surgissem vários pequenos reinos na ilha de Bissau.

Ilustração da visita a Bissau, como parte da expedição francesa capitaneada por Gaspard Théodore Mollien, realizadas em 1818, num demonstrado interesse francês pela Guiné-Bissau. O contacto dos europeus com as povoações de Bissau iniciou-se ainda em 1687, quando o rei (ou régulo) de Bissau Bacampolo-Có concordou com as propostas do Império Português em construir ali uma fortificação (1ª vez), a Fortaleza de Nossa Senhora da Conceição, estrutura que serviria de suporte ao entreposto comercial dos portugueses. Em 1690 já eram inaugurados o Hospício de Bissau (actual Hospital Nacional Simão Mendes) e a capela de Bissau.

Após a conclusão da fortaleza da Amura (1766), os portugueses defrontaram-se com muitas rebeliões nativas e sublevações de soldados, algumas das quais teve rápido êxito ao controlar, enquanto que outras somente após negociações diplomáticas conseguiu debelar o conflito. A primeira das grandes rebeliões se deu entre 29 de novembro de 1794 e 18 de julho de 1795, com os reinos papéis mantendo, durante oito meses, um cerco à fortaleza da Amura; neste mesmo ano os soldados portugueses sublevam-se pela primeira vez, alegando cansaço do cerco, obrigando o capitão-mor de Bissau a fugir.

Em 30 de março de 1834 pela primeira vez Bissau passa a ser a sede do governo colonial, recebendo o nome de "São José de Bissau", embora ainda subordinado ao governo-geral de Cabo Verde. O ato de instalação viria ocorrer somente em 13 de março de 1837, quando Honório Barreto assume a governadoria interina da Guiné (em 23 de maio torna-se governador efetivo). Barreto consegue costurar um tratado de paz com o régulo Ondoto, do reino de de Bissau, em 25 de dezembro de 1837, e; em 21 de novembro de 1838 Barreto celebra com Ondoto a aquisição do ilhéu do Rei, que serviria como um refúgio aos portugueses em caso de sublevação ou revoltas.

Em 1855, foi criada em Bissau uma comissão administrativa, e o pequeno vilarejo veio a ser elevado ao estatuto de vila em 29 de abril de 1858, mais apropriado para uma capital. Isso contribuiu para o seu desenvolvimento urbano, pois afirmava sua importância económica para a colónia já no século XIX. O governador-geral Barreto morre em 1859, facto que comove as populações da ilha, recebendo grandes honras em seu funeral.

Edifício do Banco Nacional Ultramarino (direito), em Bissau, no ato de sua instalação, em 1917. Por intermédio de um diploma real de 1906, o território guineense foi dividido num concelho (Bolama) e seis residências: Bissau, Cacheu, Farim, Geba, Cacine e Buba. Bissau continuava como capital do distrito de Bissau, a entidade legal predecessora do Sector Autónomo, porém perdeu mais da metade de suas terras para a formação dos distritos de Bolama, Cacine (actual Tombali) e Quinara. Em maio de 1908 explode a terceira guerra da ilha de Bissau (ou 1ª Campanha de Pacificação e Ocupação da Ilha de Bissau).

Em 22 de abril de 1950 a cidade ganha sua primeira instituição liceal, o Colégio-Liceu de Bissau

(actual Liceu Nacional Kwame N'Krumah); anteriormente, em 1946, já funcionava a Escola de Enfermagem da Guiné, a primeira instituição de ensino superior da nação, fechada no auge da Guerra de Independência da Guiné-Bissau. Foi em Bissau que ocorreu o fatídico episódio do Massacre de Pidjiguiti, ocorrido em 3 de agosto de 1959, no porto de Bissau, gatilho da guerra de independência contra o domínio português, antecedendo e provocando o início da guerrilha do Partido Africano da Independência da Guiné e Cabo Verde (PAIGC).