A Boolean permutation is called nonlinear if it has at least one nonlinear component function. All nonlinearBoolean permutations and their complements are called non-affine Boolean permutations. Any non-affine Boolean permutation is a potential candidate for bijective S-Box of block ciphers. In this paper, we find the number of n-variable non-affine Boolean permutations up to multiplicative n and show a simple method of construction of non-affine Boolean permutations. However, non-affinity property is not sufficient for S-Boxes. Nonlinearity is one of the basic properties of an S-Box. The nonlinearity of Boolean permutation is a distance between set of all non-constant linear combinations of component functions and set of all non-affine Boolean functions. The cryptographically strong S-Boxes have high nonlinearity. In this paper, we show a method of construction of 8-variable highly nonlinear Boolean permutations. Our construction is based on analytically design (8, 1), (8, 2), and (8, 3) highly nonlinear vectorial balanced functions and random permutation for other component functions.