Some of the face normals in your mesh are flipped. One method to display the face normals in Blender 2.8x is to use its new "Face Orientation" overlay.
Consistent face normals are very important, not only for the bevelling process. Amongst others they determine in which direction the vertices move when subdividing or bevelling a mesh.
Recalculating normals with Shift-N doesn't always work. It fails most notoriously on meshes with ngons or on non-manifold meshes. In this cases you have to do the clean-up manually.
Switch to Face Select mode (3), then select the inner face of the intrusion, then hit Ctrl and + on your Numbad until all the connected faces are selected. Then use "Operator Search" (F3 or Space, depending on your keymap settings), type "flip normals" and hit enter.
Bevelling your mesh should work now correctly.
Other reasons why bevelling might produce inconsistent results are
- Double Vertices
- Unapplied Scale
- N-gons