In this study, we showed the direct interaction between Mycobacterium avium subsp. paratuberculosis fibronectin attachment protein (FAP) and toll-like receptor4 (TLR4) via co-localization and binding by using confocal microscopy and co-immunoprecipitation assays. FAP triggered the expression of pro- and antiinflammatory cytokines in a TLR4-dependent manner. In addition, FAP-induced cytokine expression in bone marrow-derived dendritic cells (BMDCs) was modulated in part by glycogen synthase kinase-3 (GSK-3). FAP-induced expression of CD80, CD86, major histocompatibility complex (MHC) class I, and MHC class II in $TLR4^{+/+}$ BMDCs was not observed in $TLR4^{-/-}$ BMDCs. Furthermore, FAP induced DC-mediated $CD8^+$ T cell proliferation and cytotoxic T lymphocyte (CTL) activity, and suppressed tumor growth with DC-based tumor vaccination in EG7 thymoma murine model. Taken together, these results indicate that the TLR4 agonist, FAP, a potential immunoadjuvant for DC-based cancer vaccination, improves the DC-based immune response via the TLR4 signaling pathway.