Escherichia coli Nissle 1917 (EcN) is among the best characterised probiotics, with a proven clinical impact in a range of conditions. Despite this, the mechanisms underlying these "probiotic effects" are not clearly defined. Here we applied random transposon mutagenesis to identify genes relevant to the interaction of EcN with intestinal epithelial cells. This demonstrated mutants disrupted in the kfiB gene, of the K5 capsule biosynthesis cluster, to be significantly enhanced in attachment to Caco-2 cells. However, this phenotype was distinct from that previously reported for EcN K5 deficient mutants (kfiC null mutants), prompting us to explore further the role of kfiB in EcN:Caco-2 interaction. Isogenic mutants with deletions in kfiB (EcNΔkfiB), or the more extensively characterised K5 capsule biosynthesis gene kfiC (EcNΔkfiC), were both shown to be capsule deficient, but displayed divergent phenotypes with regard to impact on Caco-2 cells. Compared with EcNΔkfiC and the EcN wild-type, EcNΔkfiB exhibited significantly greater attachment to Caco-2 cells, as well as apoptotic and cytotoxic effects. In contrast, EcNΔkfiC was comparable to the wild-type in these assays, but was shown to induce significantly greater COX-2 expression in Caco-2 cells. Distinct differences were also apparent in the pervading cell morphology and cellular aggregation between mutants. Overall, these observations reinforce the importance of the EcN K5 capsule in host-EcN interactions, but demonstrate that loss of distinct genes in the K5 pathway can modulate the impact of EcN on epithelial cell health.