diff --git a/salt/map.jinja b/salt/map.jinja
index 5df6d2b..39ccc6a 100644
--- a/salt/map.jinja
+++ b/salt/map.jinja
@@ -95,9 +95,15 @@
 Debian:
   pkgs:
   - salt-minion
+  dependency_pkgs:
   - python-m2crypto
   - python-psutil
   - python-yaml
+  - python-msgpack
+  dependency_pkgs_pip:
+  - PyYAML
+  - M2Crypto
+  - psutil
   cert_pkgs:
   - ca-certificates
 Gentoo:
@@ -109,9 +115,14 @@
 RedHat:
   pkgs:
   - salt-minion
+  dependency_pkgs:
   - m2crypto
   - psutils
   - PyYAML
+  dependency_pkgs_pip:
+  - PyYAML
+  - M2Crypto
+  - psutil
   cert_pkgs:
   - ca-certificates
 {%- endload %}
diff --git a/salt/minion/grains.sls b/salt/minion/grains.sls
index df5205b..9920082 100644
--- a/salt/minion/grains.sls
+++ b/salt/minion/grains.sls
@@ -40,6 +40,8 @@
 salt_minion_grain_{{ service_name }}_{{ name }}_validity_check:
   cmd.wait:
     - name: python -c "import yaml; stream = file('/etc/salt/grains.d/{{ name }}', 'r'); yaml.load(stream); stream.close()"
+    - require:
+      - pkg: salt_minion_dependency_packages
     - watch:
       - file: salt_minion_grain_{{ service_name }}_{{ name }}
     - watch_in:
diff --git a/salt/minion/service.sls b/salt/minion/service.sls
index 7951b2f..36d8aff 100644
--- a/salt/minion/service.sls
+++ b/salt/minion/service.sls
@@ -10,12 +10,20 @@
   - version: {{ minion.source.version }}
   {%- endif %}
 
+salt_minion_dependency_packages:
+  pkg.installed:
+  - pkgs: {{ minion.dependency_pkgs }}
+
 {%- elif minion.source.get('engine', 'pkg') == 'pip' %}
 
 salt_minion_packages:
   pip.installed:
   - name: salt{% if minion.source.version is defined %}=={{ minion.source.version }}{% endif %}
 
+salt_minion_dependency_packages:
+  pkg.installed:
+  - pkgs: {{ minion.dependency_pkgs_pip }}
+
 {%- endif %}
 
 /etc/salt/minion.d/minion.conf:
@@ -57,6 +65,9 @@
   service.running:
     - name: {{ minion.service }}
     - enable: true
+    - require:
+      - pkg: salt_minion_packages
+      - pkg: salt_minion_dependency_packages
     {%- if grains.get('noservices') %}
     - onlyif: /bin/false
     {%- endif %}
@@ -81,5 +92,8 @@
     - name: 'saltutil.sync_all'
     - onchanges:
       - service: salt_minion_service
+    - require:
+      - pkg: salt_minion_packages
+      - pkg: salt_minion_dependency_packages
 
 {%- endif %}