  We consider six and four dimensional ${\cal N}=1$ supersymmetric orientifolds
of Type IIB compactified on orbifolds. We give the conditions under which the
perturbative world-sheet orientifold approach is adequate, and list the four
dimensional ${\cal N}=1$ orientifolds (which are rather constrained) that
satisfy these conditions. We argue that in most cases orientifolds contain
non-perturbative sectors that are missing in the world-sheet approach. These
non-perturbative sectors can be thought of as arising from D-branes wrapping
various collapsed 2-cycles in the orbifold. Using these observations, we
explain certain ``puzzles'' in the literature on four dimensional orientifolds.
In particular, in some four dimensional orientifolds the ``naive'' tadpole
cancellation conditions have no solution. However, these tadpole cancellation
conditions are derived using the world-sheet approach which we argue to be
inadequate in these cases due to appearance of additional non-perturbative
sectors. The main tools in our analyses are the map between F-theory and
orientifold vacua and Type I-heterotic duality. Utilizing the consistency
conditions we have found in this paper, we discuss consistent four dimensional
chiral ${\cal N}=1$ Type I vacua which are non-perturbative from the heterotic
viewpoint.
