My main development platform is Ubuntu. The cross-compilation feature is removed from PyInstaller since 1.5. In this article, I'll show you how to package a Windows executable from Python scripts using PyInstaller under wine). 
1. Build a Windows excutable on Ubuntu
Step 1: Install wine and Python
sudo apt-get install wine winetricks
winetricks python 
# Python installation directory 
$ cd ~/.wine/drive_c/Python26
Note that python 2.6 is installed, not including pip (is used to install pyinstaller). Fortunately, newer Python versions already include pip. Choose the proper version from Download Python (for me, python-2.7.10.msi) and install it on wine by:  
$ wine msiexec /i python-2.7.10.msi /L*v log.txt
Step 2: Install PyInstaller on wine
$ cd ~/.wine/drive_c/Python27
$ wine python.exe Scripts/pip.exe install pyinstaller
Successfully installed pyinstaller-3.1.1 pypiwin32-219
Step 3: Package Python scripts
Package Python scripts (e.g., HelloWorld.py) with pyinstaller.
# run `pyinstaller` under the same directory as Python scripts
$ wine ~/.wine/drive_c/Python27/Scripts/pyinstaller.exe --onefile HelloWorld.py
# filename: HelloWorld.py
#!/usr/bin/env python
# -*- coding: utf-8 -*-
print('Hello World!')
The Windows executable file is located in dist/.
$ wine dist/HelloWorld.exe 
Hello World!
fixme:msvcrt:__clean_type_info_names_internal (0x1e24e5b8) stub
2. Troubleshooting
2.1 ImportError: No module named
I package a Python script imported openpyxl, but encounter the issue ImportError: No module named openpyxl while running the Windows exculable.
$ cd ~/.wine/drive_c/Python27/Scripts/dist
$ wine ProcessSpreadsheet.exe 
Traceback (most recent call last):
  File "<string>", line 4, in <module>
ImportError: No module named openpyxl
ProcessSpreadsheet returned -1
fixme:msvcrt:__clean_type_info_names_internal (0x1e24e5b8) stub
To tackle this issue, append the openpyxl path (~/.wine/drive_c/Python27/Lib/site-packages) to pathex in the Analysis object in the application spec file (ProcessSpreadsheet.spec). 
# Step 1: install the python module, openpyxl
$ wine python.exe Scripts/pip.exe install openpyxl
# Step 2: add the `openpyxl` path 
a = Analysis(['ProcessSpreadsheet.py'],
             pathex=['C:\\Python27\\Scripts', '~/.wine/drive_c/Python27/Lib/site-packages'],
             binaries=None,
             datas=None,
             hiddenimports=[],
             hookspath=[],
             runtime_hooks=[],
             excludes=[],
             win_no_prefer_redirects=False,
             win_private_assemblies=False,
             cipher=block_cipher)
# Step 3: rebuild
$ wine pyinstaller.exe ProcessSpreadsheet.spec
References:
[1] AskUbuntu: Install Python in Wine
[2] StackOverflow: pyInstaller: Import Error
[3] StackOverflow: Cross-compiling a Python script on Linux into a Windows executable