We report evidence of a narrow structure, X(5568), in the decay sequence X(5568)→B0sπ±, B0s→J/ψϕ, J/ψ→μ+μ−, ϕ→K+K−. This is evidence for the first instance of a hadronic state with valence quarks of four different flavors. The mass and natural width of this state are measured to be m=5567.8±2.9(stat)+0.9−1.9(syst) MeV/c2 and Γ=21.9±6.4(stat)+5.0−2.5(syst) MeV/c2. If the decay is X(5568)→B∗sπ±→B0sγπ± with an unseen γ, m(X(5568)) will be shifted up by m(B∗s)−m(B0s)∼49 MeV/c2. This measurement is based on 10.4 fb−1 of pp¯ collision data at s√ = 1.96 TeV collected by the D0 experiment at the Fermilab Tevatron collider.