We consider non-perturbative six dimensional N = 1 space-time supersymmetri
c orientifolds of Type IIB on K3 with non-trivial NS-NS B-flux. All of thes
e models are non-perturbative in both orientifold and heterotic pictures. T
hus, some states in such compactifications arise in "twisted" open string s
ectors which lack world-sheet description in terms of D-branes. We also dis
cuss their dual F-theory compactifications on certain Voisin-Borcea orbifol
ds. In particular, the explicit construction of non-perturbative K3 orienti
folds with NS-NS B-flux gives additional evidence for the conjectured exten
sion of Nikulin's classification in the context of Voisin-Borcea orbifolds.
(C) 1999 Published by Elsevier Science B.V. All rights reserved.